package Graph.graphWithNoweight.dfs;


import java.util.ArrayList;

/**
 * @Author: 蔡翔
 * @Date: 2020/2/7 12:05
 * @Version 1.0
 *
 * 利用 dfs 检测是否为二分图
 */
public class BipartitionDetection {
    private Graph G;
    private boolean[] visited;
    //引入 color 是为了对每个顶点进行染色，，这个很关键，每条边两头不同（dfs的递归遍历是判断的关键），是判断二分图的关键。
    private int[] colors;
    private boolean isBipartite = true;


    private ArrayList<Integer> order = new ArrayList<>();

    public BipartitionDetection(Graph G){
        this.G = G;
        visited = new boolean[G.V()];
        colors = new int[G.V()];
        for(int i=0;i<G.V();i++){
            colors[i] = -1;
        }
        for(int v=0;v<G.V();v++){
            if(!visited[v]){
                if(!dfs(v,0)){
                    isBipartite = false;
                    break;
                };
            }
        }
    }

    public boolean isBipartite(){
        return this.isBipartite;
    }

    //代表v 这个顶点会被染成 color 这个颜色
    //return true代表是二分图，， false代表不是二分图
    private boolean dfs(int v,int color) {
        visited[v] = true;
        order.add(v);
        colors[v] = color;
        for(int w:G.adj(v)){
            if(!visited[w]){
                //1-color 就是在1 和0 之间来回变换。
                if(!dfs(w,1-color)){
                    return false;
                };
            } else if(colors[w] == colors[v]){
                //进入else if 说明已经被染色了，，并且 这条边的两端 是同色的 ，说明就不是二分图
                return false;
            }
        }
        return true;
    }

    public Iterable<Integer> order(){
        return order;
    }

    public static void main(String[] args) {
        Graph g = new Graph("g.txt");
        BipartitionDetection graphDFS = new BipartitionDetection(g);
        System.out.println(graphDFS.isBipartite());

        Graph g2 = new Graph("g2.txt");
        BipartitionDetection bipartitionDetection2 = new BipartitionDetection(g2);
        System.out.println(bipartitionDetection2.isBipartite());
    }

}
